package com.algorithm.排序.基于比较的排序;

import com.algorithm.排序.Sort;

@SuppressWarnings("all")
//顺序 123456789
public class 归并排序<T extends Comparable<T>> extends Sort<T> {

    //直接根据大数组的一般分配一个左边的数组，并且将它变成一个成员变量，目的是避免频繁的创建数组
    private T[] leftArray;

    @Override
    protected void sort() {
        leftArray =(T[]) new Comparable[array.length >> 1];
        sort(0,array.length);
    }

    //
    /**
     * 对[begin,end] 范围的数据进行归并排序
     */
    private void sort(int begin,int end) {
        if (end - begin < 2) return;

        int mid = (begin + end) >> 1;

        sort(begin, mid);
        sort(mid, end);

        merge(begin, mid, end);
    }

    /**
     * 将 [begin,mid]和[mid,end] 范围的序列合并成一个有序序列
     * @param begin
     * @param mid
     * @param end
     */
    private void merge(int begin, int mid, int end) {
        //定义li（ledtIndex）左边数组的头指针，以及le左边数组的尾指针
        int li = 0 , le = mid - begin;
        //定义ri（rightIndex）右边数组的头指针，以及re右边数组的尾指针
        int ri = mid , re = end;
        //定义大数组的头指针
        int ai = begin;

        //备份左边的数组
        for (int i = li; i < le; i++) {
            //从大数组的第 begin+1 个数值赋给备份的左边数组
            leftArray[i] = array[begin + i];
        }

        //如果左边未结束
        while (li < le) {
            //如果左边数组第ri个元素 小于 右边数组第li个元素，
            //并且右边没有结束
            if (ri < re && cmp(array[ri], leftArray[li]) < 0) {
                //将左边数组的第ri个元素赋值给大数组的第ai个元素
                //ai,li指针往后移一位
                array[ai++] = array[ri++];

                // 大于
            }else {
                //将右边数组的第li个元素赋值给大数组的第ai个元素
                //ai,ri指针往后移一位
                array[ai++] = leftArray[li++];

            }
        }

/*        //如果左边未结束
        while (li < le) {
            //如果左边数组第li个元素 小于等于 右边数组第ri个元素，（加等于是为了将算法变成稳定的算法）
            //并且右边没有结束
            if (ri < re && cmp(leftArray[li],array[ri]) <= 0){
                //将左边数组的第li个元素赋值给大数组的第ai个元素
                array[ai] = leftArray[li];
                //ai,li指针往后移一位
                ai++;
                li++;
            // 大于
            }else {
                //将右边数组的第ri个元素赋值给大数组的第ai个元素
                array[ai] = array[ri];
                //ai,ri指针往后移一位
                ai++;
                ri++;
            }
        }*/
    }
}
